1. Field of the Invention
The present invention relates to the conversion from odd to non-zero winding number convention for the representation of polygons in a graphics system and, more particularly, to the conversion from odd to non-zero winding number convention using an extended frame buffer.
2. Description of the Related Art
Copending U.S. patent application Ser. No. 07/363,827 describes a frame-buffer extension which allows the representation of polygons defined by a non-zero winding number. The advantage of this approach is that the polygons can be represented by just their borders, and many polygons can be included in the frame buffer even if they overlap. Multiple shapes defined by boundaries and a non-zero winding number can co-exist in the frame buffer. Many objects can be entered at a cost proportional to their perimeters rather than their areas, as is the case for conventional methods. Filling of all interiors can be performed in a single step as the frame buffer is imaged. Defining polygons, however, by a non-zero winding number is unusual. Most graphics systems define polygon interiors by an odd winding number. Page-description languages, such as Interpress and PostScript, support both odd- and non-zero winding number definitions. Of course, the scheme proposed could be used with a new graphics system which supported only the non-zero winding number definition, but if it is to be useful in implementing more conventional systems, then a method for converting from the odd to non-zero winding number convention is needed.
The related art has disclosed graphics systems having the ability to represent polygonal areas.
U.S. Pat. No. 4,697,178 to Heckel discloses a graphics system which utilizes a scanline depth buffer algorithm to display a three-dimensional scene on a two-dimensional display device.
U.S. Pat. No. 4,646,078 to Knierim et al. discloses a graphics system with a frame buffer memory for rapid shading of predetermined shapes. The frame buffer has two sections, one for receiving image information and the other for receiving patterns used in filling the predetermined images.
U.S. Pat. No. 4,625,289 to Rockwood discloses an improved Z-buffer for use in a graphics system. An exhaustive sampling method employs a surface scan to fill the buffer and a coordinate testing means to eliminate hidden surfaces.
U.S. Pat. No. 4,594,673 to Holly discloses a hidden surface processor for interaction with a graphics system. A hidden surface algorithm assembles and stores ordered linked lists of data concerning the segments which form each scan line.
U.S. Pat. No. 4,815,009 to Blatin discloses an algorithm for filling an image outline wherein an odd winding number is used to describe a line. Two methods of filling a polygon are shown which use a non-zero winding number or an odd winding number.
U.S. Pat. No. 4,897,805 to Wang discloses a method and apparatus for reforming polygon fills wherein an algorithm is shown which allows complex polygon shapes to be more easily filled. When scanning a polygon, the algorithm determines whether a string of pixels between one intersected polygon edge and the next intersected polygon edge should be filled when multiple horizontal edges are encountered.
The related art provides no suggestion of a conversion method which could be utilized to convert the odd winding number convention to the non-zero winding number convention.